//给定两个字符串 s 和 t ，它们只包含小写字母。 
//
// 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。 
//
// 请找出在 t 中被添加的字母。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abcd", t = "abcde"
//输出："e"
//解释：'e' 是那个被添加的字母。
// 
//
// 示例 2： 
//
// 
//输入：s = "", t = "y"
//输出："y"
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 1000 
// t.length == s.length + 1 
// s 和 t 只包含小写字母 
// 
// Related Topics 位运算 哈希表 字符串 排序 👍 327 👎 0


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution389 {
    public char findTheDifference(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        char[] sarr = s.toCharArray();
        for (int i = 0; i < sarr.length; i++) {
            map.put(sarr[i], map.getOrDefault(sarr[i], 0) + 1);
        }
        char[] tarr = t.toCharArray();
        for (int i = 0; i < tarr.length; i++) {
            int count = map.getOrDefault(tarr[i], 0);
            if (count == 0) {
                return tarr[i];
            } else {
                map.put(tarr[i], count - 1);
            }
        }
        return ' ';
    }
}
//leetcode submit region end(Prohibit modification and deletion)
